package j2025.j03;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author 猫大仙
 */
public class j0304 {
    /**
     * 1768. 交替合并字符串
     * 给你两个字符串 word1 和 word2 。
     * 请你从 word1 开始，通过交替添加字母来合并字符串。
     * 如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
     *
     * 返回 合并后的字符串 。
     * @param word1
     * @param word2
     * @return
     */
    public String mergeAlternately(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if(m==0){
            return word2;
        }
        if(n==0){
            return word1;
        }
        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        while(i<m && j<n){
            sb.append(word1.charAt(i++));
            sb.append(word2.charAt(j++));
        }
        while(i<m){
            sb.append(word1.charAt(i++));
        }
        while(j<n){
            sb.append(word2.charAt(j++));
        }
        return sb.toString();
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        //初始化队列,确保队列中的元素对应的值是递减的
        for (int i = 0; i < k; i++) {
            //如果当前元素的值大于等于队列末尾元素的值，则移除队列末尾的元素
            if(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        int[] ret = new int[n-k+1];
        ret[0] = nums[deque.peekFirst()];

        //处理剩余队列
        for (int i = k; i < n; i++) {
            //维护队列
            if(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);

            //保证队列中的元素都在窗口内
            while (deque.peekFirst() <= i-k){
                deque.pollFirst();
            }

            //更新数据
            ret[i-k+1] = nums[deque.peekFirst()];
        }
        return ret;
    }
}
